package com.zwj.interview.两数和;

/**
 * 输入一个递增排序的数组和一个值k，请问如何在数组中找出两个和为k的数字并返回它们的下标？
 * 假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。
 * 例如，输入数组[1，2，4，6，10]，k的值为8，数组中的数字2与6的和为8，它们的下标分别为1与3
 * 这道题最突出的特点就是元素有序
 */
public class 两数和1之二分 {

    /**
     * 我们用两个指针P1和P2分别指向数组中的两个数字。指针P1初始化指向数组的第1个（下标为0）数字，指针P2初始化指向数组的最后一个数字。
     * 如果指针P1和P2指向的两个数字之和等于输入的k，那么就找到了符合条件的两个数字。如果指针P1和P2指向的两个数字之和小于k，
     * 那么我们希望两个数字的和再大一点。由于数组已经排好序，因此可以考虑把指针P1向右移动。因为在排序数组中右边的数字要大一些，
     * 所以两个数字的和也要大一些，这样就有可能等于输入的数字k。同样，当两个数字的和大于输入的数字k时，可以把指针P2向左移动，
     * 因为在排序数组中左边的数字要小一些
     *
     * @param numbers
     * @param target
     * @return
     *
     * 注意:能这么做的前提就是数组有序
     */
    public int[] twoSum(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length - 1;
        while (i < j && numbers[i] + numbers[j] != target) {
            if (numbers[i] + numbers[j] < target) {
                i++;
            } else {
                j--;
            }
        }
        return new int[]{i, j};
    }



}
